Turbo coding is a type of error correcting coding used in communication systems. Turbo coding has been shown to allow the operation of communication channels closer to the theoretical Shannon limit than prior coding schemes. Prior to the development of turbo coding, the most powerful error correcting coding was performed by convolutional encoders and Viterbi decoders or using block codes (e.g., Reed-Solomon codes). In its most basic form, turbo encoding uses two parallel convolutional encoders, referred to as “constituent encoders,” with some form of interleaving in between them. The channel data comprises the bit stream describing the original information, the parity bits generated by the first constituent encoder, and the parity bits generated by the second constituent encoder.
Turbo decoding, like the decoding of other types of error correcting codes, involves making decisions based upon codeword probabilities. Turbo decoding is a type of iterative soft-decision decoding, in which the decoder is provided with extrinsic information indicating a measure of confidence for the decision. A conceptual structure of a turbo decoder 100 is illustrated in FIG. 1. Turbo decoder 100 includes two soft-input soft-output (SISO) decoders 102 and 104, coupled in a cyclic topology with interleaver memory 106 (sometimes referred to by the symbol “π”) and de-interleaver memory 108 (sometimes referred to by the symbol “π−1”). The iterative nature of turbo decoder operation can be described in terms of half-iterations. A half-iteration can be defined as the work done by one of SISO decoders 102 and 104 reading from one of interleaver and de-interleaver memories 106 and 108, processing the received block of code symbols, and writing the results into the other of de-interleaver and interleaver memories 108 and 106, respectively. The overall decoding process consists of many half-iterations.
Each SISO decoder 102 and 104 is provided with channel observations, processes the channel observations in accordance with an algorithm or processing method, and outputs soft information in the form of a log likelihood ratio that can be used to make a hard decision about the received information or can be used for further processing. The soft information is probability data for the received information that provides an indication of the confidence that is to be attributed to the value of the received information. For example, if the received information was decoded to be a “0” bit, the soft information associated with that received information gives an indication of the likelihood that the original information (before coding) was indeed a “0” bit. The SISO decoder also generates additional soft information as it is processing the input information; the difference between the additional generated soft information and the soft information at the input is called extrinsic information. In many applications where a SISO decoder is used, the extrinsic information is recursively inputted as soft input information to allow the SISO to generate more reliable soft information about particular received information.
The channel observations with which SISO decoders 102 and 104 are provided include the systematic (Rs) and parity bit (Rp) samples that are part of the received codeword information block. The logMAP (Maximum A Posteriori) algorithm is perhaps the most commonly used algorithm under which SISO decoders 102 and 104 operate. In a turbo decoder in which they operate under the logMAP algorithm, they are generally referred to as logMAP processors. The logMAP algorithm is a recursive algorithm for calculating the probability of a processing device being in a particular state at a given time based on received information. The probabilities are calculated by forward recursions and backward recursions over a defined time window or a block of information. The logMAP algorithm essentially is the recursive calculation of probabilities of being in certain states based on received information and the a priori probabilities of going to specific states from particular states. The states describe the condition of a process that generates the information that is ultimately received.
The logMAP algorithm and how a logMAP processor operates are often represented by a trellis diagram having a certain number of states. Each state has a probability associated with it and transition probabilities indicating the likelihood of transitioning from one state to another state either forward or backward in time. In general, each state in a trellis has a number of transition probabilities entering it and leaving it. The number of probabilities entering or leaving states of a trellis is referred to as the radix. Thus, in a Radix-2 trellis, each state has two entering and two exiting transition probabilities. The trellis shows the possible transition between states over time. In general, a Radix-K trellis has K branches entering and K branches leaving each state in the trellis. The output of the logMAP algorithm is called the LLR (Log Likelihood Ratio), which represents the probability that the original information (i.e., information prior to exposure to any noisy environment and prior to any processing) was a certain value. For example, for digital information, the LLR represents the probability that the original information was either a “0” bit or a “1” bit given all of the received data or observations.
The logMAP algorithm is typically implemented by performing forward and backward recursions over the trellis. The probabilities of each state in the trellis in the forward direction, known as alpha (“α”) values, are determined in the forward recursion. The probabilities of each state in the trellis in the reverse direction, known as beta (“β”) values, are determined in the backward recursion. Each branch in the trellis has a transition probability associated with its connection from one state to the next, and this is known as the branch metric or gamma (“γ”). The gamma values are calculated during each of the forward and backward recursions.
The logMAP turbo decoding process can be summarized in the form of the following sequence of steps or equations, well-known to practitioners in the art:
(1A) Read (“old”) extrinsic value from a previous half-iteration from interleaver memory:
      L    ext    old    =      read    ⁡          (      INTERLEAVER      )      
(2A) Compute the branch metrics for all branches in the trellis:
      γ    =                  1        2            ⁡              [                                            (                                                R                  s                                +                                  L                  ext                  old                                            )                        ×                          E              s                                +                                    R              p                        ×                          E              p                                      ]              ,where Es and Ep represent the expected systematic and parity bits for the transition.
(3A) Perform a forward recursion on the trellis by computing an alpha value for each trellis node:αtφ(t)=logsum(αt−1φ(t−1)+γt0,αt−1φ′(t−1)+γt1),where φ(t−1) and φ′(t−1) represent the source trellis state transitioning to destination state φ(t) for a “0” and “1” bit, respectively.
(4A) Perform a backward recursion on the trellis by computing a beta value for each trellis node:βtφ(t)=logsum(βt+1φ′(t+1)+γt0,βt+1100 (t+1)+γt1)
(5A) Compute the log likelihood (LL) for each time t for “0” bit:
            LL      t      0        =                            logsum                      N            -            1                                    i          =          0                    ⁡              (                              α            t                          φ              ⁡                              (                t                )                                              +                      γ            t            0                    +                      β                          t              +              1                                      φ              ⁡                              (                                  t                  +                  1                                )                                                    )              ,where N is the number of states in the trellis.
(6A) Compute the log likelihood (LL) for each time t for “1” bit:
      LL    t    1    =                    logsum                  N          -          1                            i        =        0              ⁡          (                        α          t                                    φ              ′                        ⁡                          (              t              )                                      +                  γ          t          1                +                  β                      t            +            1                                              φ              ′                        ⁡                          (                              t                +                1                            )                                          )      
(7A) Compute the log likelihood ratio (LLR):LLR=LLt1−LLt0
(8A) Compute the extrinsic value to be fed to the next half-iteration:
      L    ext    new    =      LLR    -          L      ext      old      
(9A) Store new extrinsic value in interleaver memory:
  store  ⁡      (          INTERLEAVER      ,              L        ext        new              )  
(10A) Test to determine whether to terminate the iterative process. If the iteration limit is reached, or if a test for early termination passes, then stop the iterative process, as this indicates the block has been sufficiently decoded.
(11A) If the iterative process is not yet terminated, then repeat the above-listed Steps 1A-10A, with iterations alternating between a linear addressing mode and an interleaved addressing mode.
Practitioners in the art have constructed and made commercially available turbo decoders that implement the above-described method. It can be appreciated that the interleaver memory in such turbo decoders may need to store several thousand extrinsic values, as there is one extrinsic value per information bit represented in the code block. An important objective in chip design is to conserve resources such as the amount of memory. The present invention addresses memory conservation and other problems, such as, for example, quantization loss in the branch metric calculations, etc., in the manner described below.